import random
import heapq
import time
import numpy as np

# Chaque arête est dirigée et pèse des minutes
dict_reseau = {
    "Gare":      {"Centre": 5, "Musée": 6, "Université": 9},
    "Centre":    {"Musée": 2, "Hôpital": 4, "Rivière": 7},
    "Musée":     {"Théâtre": 3, "Centre": 3},
    "Université":{"Stade": 3, "Hôpital": 4},
    "Stade":     {"Parc": 5},
    "Hôpital":   {"Aéroport": 8, "Parc": 6},
    "Parc":      {"Rivière": 3},
    "Rivière":   {"Aéroport": 7, "Théâtre": 4},
    "Théâtre":   {"Centre": 4},
    "Aéroport":  {}
}

depart = "Gare"
arrivee = "Parc"
H = []              # Tas
distances = {}      # Distances
cles = {}           # Clés des éléments contenus dans le tas
X = []              # Liste pour stocker les vertex traités par l'algorithme


def Initialisation(reseau,depart):
    heapq.heapify(H)

    for station in reseau:
        if station == depart:
            heapq.heappush(H,(0,station))
            cles[station] = 0
        else:
            heapq.heappush(H,(np.inf,station))
            cles[station] = np.inf

def Dijkstra(reseau):
    while len(H) != 0:
        dist,w = heapq.heappop(H)

        # Test si c'est une entrée obsolete
        if w in distances:
            if distances[w] != dist:
                continue

        X.append(w)
        distances[w] = dist

        for station in reseau[w]:
            # Calcul le score de Dijkstra
            val_cle = min(cles[station],distances[w]+reseau[w][station])
            heapq.heappush(H,(val_cle,station))